package day_7_12;

public class Main1 {
    /**
     * 208. 实现 Trie (前缀树)
     * https://leetcode.cn/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-100-liked
     */
    class Trie {
        //相当于是 26 叉树

        private Trie[] children;
        // 用来判断当前节点是否是最后一个
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            // 获取当前的根节点
            Trie node = this;
            // 将word 中的单词进行取出并且对其进行插入操作
            for(int i = 0;i < word.length();i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null) {
                    // 创建一个新的
                    node.children[index] = new Trie();
                }
                node = node.children[index]; // 相当于是二叉树中的 node = node。left
            }
            // 将最后一个位置的数据置为 true
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd == true;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        public Trie searchPrefix(String prefix) {
            // 直接返回传入的字符串的最后一个单词的节点
            Trie node = this;
            for(int i = 0;i < prefix.length();i++) {
                char ch = prefix.charAt(i);
                int index = ch - 'a';
                if(node.children[index] == null) {
                    return null;
                }
                node = node.children[index];
            }
            return node;
        }
    }
}
